# !/usr/bin/python
# -*- coding: utf-8 -*-
'''
@File    :   169多元素.py
@Time    :   2021/11/04 15:28:52
@Author  :   Qingxiang Zhang
@Version :   1.0
@Contact :   344285081@qq.com
@Desc    :   分治算法的一类
@Software:    Vscode
'''

"""* 题目描述
  给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 [n/2] 的元素。
  你可以假设数组是非空的，并且给定的数组总是存在众数。
  示例 1:
  ```python
  输入: [3,2,3]
  输出: 3
  ```
  示例 2:
  输入: [2,2,1,1,1,2,2]
  输出: 2
* 解题思路
  * 确定切分的终止条件
    直到所有的子问题都是长度为 1 的数组，停止切分。
  * 准备数据，将大问题切分为小问题
    递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回
  * 处理子问题得到子结果，并合并
    - 长度为 1 的子数组中唯一的数显然是众数，直接返回即可。
    - 如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。
    - 如果他们的众数不同，比较两个众数在整个区间内出现的次数来决定该区间的众数

* 代码"""

class Solution:
    def majorityElement(self, nums) -> int:
        # 使用递归进行解析
        # 切分的终止条件
        if not nums:
          return None
        if len(nums)==1:
          return nums[0]
          # # 【准备数据，并将大问题拆分为小问题】
        left = self.majorityElement(nums[:len(nums)//2])
        right = self.majorityElement(nums[len(nums)//2:])
          # 【处理子问题，得到子结果】
        # 【对子结果进行合并 得到最终结果】
        if left == right:
          return left
        if nums.count(left) > nums.count(right):
          return left
        else:
          return right
# 实列一
# [3]   [2,3]
# 3      2        3
#  3       3
# 3
# 实列二
# [2,]

